import java.util.Random;

public class demo1 {
        public int[] sortArray(int[] nums){
            kuai(nums,0,nums.length-1);
        }
        public void kuai(int []nums, int l,int r){
            if (l>r)return;
            int key=nums[new Random().nextInt(r-l+1)+l];
            int left=l-1; int right=r+1;int i=l;
            while (i<right){
                if(nums[i]<key)swap(nums,++left,i++);
                else if(nums[i]==key)i++;
                else swap(nums,--right,i);
            }
            kuai(nums,l,left);
            kuai(nums,right,r);
        }
        public void swap(int []nums,int x,int y){
            int temp=nums[x];
            nums[x]=nums[y];
            nums[y]=temp;
        }
}
